package zw_401_500.zw_441_排列硬币;

class Solution {

    public static void main(String[] args) {
        int n = 8;
        int coins = arrangeCoins(n);
        System.out.println(coins);
    }

    /**
     * 二分查找
     * @param n
     * @return
     */
    public static int arrangeCoins(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if ((long) mid * (mid + 1) <= (long) 2 * n){
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 迭代
     * @param n
     * @return
     */
//    public static int arrangeCoins(int n) {
//        int count = 0;
//        while (n > count) {
//            n -= ++count;
//        }
//        return count;
//    }
}
